package written_examination_questions;

import java.util.Scanner;

public class Demo20251104 {
    /**
     * 最长回文子串
     * @param s
     * @return
     */
    public int getLongestPalindrome (String s) {
        // 中心扩展算法
        int n = s.length();
        int ret = 0;
        // 枚举所有的中心点
        for (int i = 0; i < n; i++) {
            // 当长度为奇数
            int left = i - 1, right = i + 1;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            ret = Math.max(ret, right - left - 1);
            // 当长度为偶数
            left = i;
            right = i + 1;
            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            ret = Math.max(ret, right - left - 1);
        }
        return ret;
    }

    /**
     * 过河卒
     * @param args
     */
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt(), x = in.nextInt(), y = in.nextInt();
        // 1.创建dp表
        // 2.填表
        // 3.初始化
        // 4.返回值
        // 状态表示 : dp[i][j]表示到达(i, j)的路径数量
        long[][] dp = new long[n + 2][m + 2];
        dp[0][1] = 1;
        x += 1; y += 1; // dp 表的位置和马的位置一一对应
        for (int i = 1; i <= n + 1; i++) {
            for (int j = 1; j <= m + 1; j++) {
                if (i != x && j != y && Math.abs(i - x) + Math.abs(j - y) == 3 || (i == x && j == y)) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        System.out.println(dp[n + 1][m + 1]);
    }

    /**
     * 买股票的最佳时机
     */
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int ret = 0, prevMin = in.nextInt(); // 首先将第一个输入的数记录为前驱最小值
        int x = 0;
        for (int i = 1; i < n; i++) {
            x = in.nextInt();
            // 更新ret
            ret = Math.max(ret, x - prevMin);
            // 更新前驱最小值
            prevMin = Math.min(prevMin, x);
        }
        System.out.println(ret < 0 ? 0 : ret);
    }
}
